package x.y.z;

public class Interview_4_6_Successor {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // 存在右子树，返回右子树的leftmost
        if (p.right != null) {
            p = p.right;
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }

        // 不存在右子树
        TreeNode node = root;
        TreeNode res = null;
        while (node != p) {
            if (p.val < node.val) {
                res = node;
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return res;
    }
}
